Public Land Mobile Networks (PLMN), such as the Global System for Mobile Communications (GSM), are designed as the wireless extension of the Public Switched Telephone Network (PSTN). Subscribers of a PLMN receive voice and data services while they are traveling within the network coverage area. To guarantee the timely and accurate delivery of incoming calls to a subscriber, a PLMN must be able to track the current location of each mobile station, or terminal. This tracking procedure is commonly referred to as location management.
Location management entails the recordation of up-to-date information on the location of each mobile terminal in a distributed network of location databases. Each mobile terminal is required to periodically report its location to the network. On receiving such information, the network updates its records in one or more location databases. When a call for such a mobile terminal arrives at a subsequent time, the location information of the mobile terminal will be retrieved from the location databases and the call is delivered accordingly.
As the number of subscribers using mobile terminals increases, the number of subscriber records that must be stored and updated in location databases increases, resulting in increased processing load on telecommunications switches and databases and increased time to access such subscriber records. As such processing load and access time increases, costs for providing such services increases, and network capacity and subscriber satisfaction diminish.
To alleviate the high processing load and access time, subscriber records are typically organized in a location database structured as a "binary tree". Conventionally, there are a number of types of binary trees available for so organizing records. For example, an optimal, or ideal, binary tree may be generated using well-known techniques wherein records with the highest access rate are placed closest to the root of the tree such that the cost of searching for such records is absolutely minimized. The cost of generating such an optimal tree is, however, generally prohibitive if the number of records to be organized is very large.
Alternatively, a relatively simple binary tree may be randomly generated which requires that subscriber records be ordered as a data structure using as an index the identity of the subscriber's mobile terminal. If a subscriber population is large, the subscriber records may first be partitioned into a number of subsets using a "hash" function. For example, the first 8 bits of the subscriber identity may be used to partition all the subscriber records into 2.sup.8, or 256, subsets. A binary tree is then generated within each subset of subscriber records. In a randomly generated binary tree, the relative position of a subscriber record depends only on the chronological order in which the records are inserted into the tree. A newly added subscriber record must be positioned at the "bottom" of the tree regardless of the rate with which the record is accessed. As a result of the order in which subscribers are added to the tree, an early subscriber record with a relatively low access rate may be located "higher" in the binary tree and, thus, more economically accessible, than a later subscriber record having a higher access rate. Such a tree, while much less costly to generate than an ideal tree, is generally much less efficient and, therefore, much more expensive to use, than the aforementioned ideal tree in which subscribers having a high access rate are located generally higher and more accessibly in the tree.
The foregoing randomly generated binary tree may be "balanced" to locate an approximately equal number of subscribers on each side of the tree. The access cost of a binary tree, however, may not necessarily decrease by being balanced and, furthermore, may still require more time to access subscribers with high access rates than subscribers with lower access rates. The efficiency of a balanced binary tree is thus not near that of an ideal binary tree.
In yet another binary tree, the subscriber records are first arranged in decreasing order of access rate. The subscriber records are then inserted into the binary tree according to such order. This method guarantees that highly accessed subscriber records are located at the top of the tree. However, this method may generate an extremely unbalanced tree which may not result in lower overall access cost compared to the randomly generated binary tree.
While there are further variations on how a binary tree may be generated using conventional techniques, as exemplified above, each such binary tree is uneconomical with respect to the cost of either generating it or of using it.
Accordingly, a continuing search has been directed to methods for generating a binary tree which can quickly and efficiently access subscriber records in location databases and that is, therefore, more economical to generate and to use than is possible with conventional binary trees.